package com.tree.leetcode;

/**
 * @ClassName com.tree.leetcode
 * Description: 阶乘
    阶乘：5！=1*2*3*4*5， 当阶乘变大时会出现很多问题，
 *     比如无法用int（范围）、double（转成科学计数、精准度，范围），long（范围）
 *      所以我们这里每次乘以一个数的时候结果放到数组中， 然后拿数组与乘数相乘
 *
 *      数组与数相乘算法：372*18
 *      1. 乘数与每位相乘，
 *      2 留位与进位：当前位留下来，不在当前位的往前进位，如个位36，6留下来，3往十位进位，原来十位126+3=129，那么十位留9，百位进12， 那么百位变为54+12=66， 百位留6，千位进6，最终结果为6696）
 *      3        7       2
 *                      18
 *  -------------------------
 *      54      126     36
 *
 *      注意进位， 个位进3， 十位变为129， 十位进12， 百位变为54+12=66，进6， 千位变为6 * @Author tree
 * @Date 2020-03-13 23:23
 * @Version 1.0
 */
public class Factorial {

    public static void main(String[] args) {
        //容纳大数据的数组
        int[] data = new int[5];
        //5的阶乘
        int num = 5;

        //第一位为1
        data[data.length-1] = 1;


        //阶乘， 遍历每位数字相乘
        for(int i =1 ;i <= num;i++){
            //每个阶段其实就是一个数组与一个数字相乘
            data = bigDataMulti(data,i);
        }

        //打印
        for (int i = 0; i < data.length; i++) {
            System.err.print(data[i]);
        }


    }

    /**
     * 大数与一个数相乘
     *
     * @param data
     * @param multi
     * @return
     */
    public static int[] bigDataMulti(int[] data, int multi){

        //按每列与乘数相乘, 得出未进位的数组
        for(int i = 0; i< data.length;i++){
            data[i] = data[i]*multi;
        }


        //进或留, 从末尾即个位开始算起
        for(int i = data.length-1; i>0; i-- ){
            //进位， 除以10之后的数+当前数字
            data[i-1] += data[i]/10;
            //取余：余数在当前位留下 , %
            data[i] = data[i]%10;

        }
        return data;
    }
}
